package 单周赛.history;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *
 */
public class 第331场单周赛 {

    public static void main(String[] args) {

        System.out.println(pickGifts(new int[]{1, 1, 1, 1}, 4));

        vowelStrings(new String[]{
                        "a", "0", "e"},
                new int[][]{{0, 2}});

        System.out.println(minCapability2(new int[]{2, 3, 5, 9}, 2));

    }

    /**
     * 优先队列
     */
    public static long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);
        for (int gift : gifts) {
            priorityQueue.add(gift);
        }

        while (k-- > 0) {
            Integer gift = priorityQueue.poll();
            int sqrt = (int) Math.sqrt(gift);
            priorityQueue.add(sqrt);
        }

        long sum = 0;
        while (!priorityQueue.isEmpty()) {
            sum += priorityQueue.poll();
        }

        return sum;
    }

    /**
     * 前缀和
     */
    public static int[] vowelStrings(String[] words, int[][] queries) {
        int[] prefixSum = new int[words.length];
        if (isYuanYin(words[0])) {
            prefixSum[0] = 1;
        }

        for (int i = 1; i < words.length; i++) {
            prefixSum[i] = prefixSum[i - 1];
            if (isYuanYin(words[i])) {
                prefixSum[i]++;
            }
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = prefixSum[queries[i][1]];
            if (queries[i][0] > 0) {
                ans[i] -= prefixSum[queries[i][0] - 1];
            }
        }

        return ans;

    }

    private static boolean isYuanYin(String word) {
        char b = word.charAt(0);
        char e = word.charAt(word.length() - 1);
        if (b == 'a' || b == 'o' || b == 'e' || b == 'i' || b == 'u') {
            if (e == 'a' || e == 'o' || e == 'e' || e == 'i' || e == 'u') {
                return true;
            }
        }
        return false;
    }


    /**
     * 动态规划
     * 1，子问题
     * dp[i][j] 表示在 [0,i] 的房子中，偷 j 个房子的最大窃取价值
     * 时间复杂度：O(n^2) 超时！！！
     */
    public static int minCapability(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        int[] pre2Arr = new int[k + 1];
        int[] pre1Arr = new int[k + 1];
        pre1Arr[0] = 0;
        pre1Arr[1] = nums[0];
        if (k == 1) {
            ans = Math.min(ans, nums[0]);
        }

        for (int i = 1; i < nums.length; i++) {
            int[] curArr = new int[k + 1];
            curArr[1] = Math.min(nums[i], pre1Arr[1]);
            for (int j = 2; j <= k; j++) {
                // 不偷当前房屋
                curArr[j] = pre1Arr[j];

                if (i - 2 >= 0 && pre2Arr[j - 1] > 0) {
                    if (curArr[j] == 0) {
                        curArr[j] = Math.max(pre2Arr[j - 1], nums[i]);
                    } else {
                        curArr[j] = Math.min(curArr[j], Math.max(pre2Arr[j - 1], nums[i]));
                    }
                }
            }

            pre2Arr = pre1Arr;
            pre1Arr = curArr;

            if (curArr[k] > 0) {
                ans = Math.min(ans, curArr[k]);
            }
        }
        return ans;
    }

    /**
     * 动态规划+二分查找(时间复杂度 n*log(n))
     * 1，窃取能力和能窃取的最多房屋数量是成正比的，二分
     * 枚举窃取能力，如果房屋 >= k，那么当前窃取能力是
     * 符合规则的
     * 2，如何求每个窃取能力可以窃取的最多房屋数量，
     * 动态规划，如果 nums[i] <= capacity，有两种方案
     * 窃取或者不窃取，取较多的，否则只有不窃取一种方案
     */
    public static int minCapability2(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        int left = 0, right = Arrays.stream(nums).max().getAsInt();

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pre2Cnt = 0, pre1Cnt = 0, curCnt;
            for (int i = 0; i < nums.length; i++) {
                // 不偷
                curCnt = pre1Cnt;
                if (nums[i] <= mid) {  // 偷
                    curCnt = Math.max(curCnt, pre2Cnt + 1);
                }
                pre2Cnt = pre1Cnt;
                pre1Cnt = curCnt;
            }
            if (pre1Cnt >= k) {
                ans = Math.min(ans, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

}
